rtk 1998

1998.1.2

1. podnaloga

Pri predmetu programiranja so učenci sestavili lasten program za urejanje besedila. Med drugimi so napisali funkcije brisi_znak, vrini_izbrisano in vrini_presledek. (Opise funkcij najdeš spodaj.)

Naloga

Preuredi vrstice funkcije pregledna_stevila(stevilo), ki naredi števila bolj pregledna, pri tem pa uporablja spodnje funkcije. Na vsaka tri mesta v številu vrine presledek.

zacasni_pomnilnik = ''

def brisi_znak(niz, i):
    '''zbriše znak na i-tem mestu v nizu in ga shrani v zacasni pomnilnik'''

    if i >= len(niz):
        return niz

    global zacasni_pomnilnik
    zacasni_pomnilnik = niz[i]
    return niz[:i] + niz[i+1:]


def vrini_izbrisano(niz, i):
    '''na i-to mesto v nizu vrine znake iz začasnega pomnilnika'''

    if i > len(niz):
        return niz
    elif i == len(niz):
        return niz + zacasni_pomnilnik
    else:
        return niz[:i] + zacasni_pomnilnik + niz[i:]


def vrini_presledek(niz, i):
    '''na i-to mesto v nizu vrine presledek'''

    if i > len(niz):
        return niz
    elif i == len(niz):
        return niz + ' '
    else:
        return niz[:i] + ' ' + niz[i:]


st_presledkov = 0
pregledno_stevilo = vrini_presledek(pregledno_stevilo, i+st_presledkov)
def pregledna_stevila(stevilo):
st_presledkov += 1
n = len(stevilo)
return pregledno_stevilo[::-1]
while i < n:
i += 3
pregledno_stevilo = stevilo[::-1]
i = 3

Vhodni podatki

Cela števila zapisana v obliki niza.

Izhodni podatki

Vrne niz števila z ustreznimi presledki med vsakimi tremi števkami.

Primer

Vhod

>>> pregledna_stevila('12345')

Izhod

'12 345'

Uradna rešitev

zacasni_pomnilnik = ''

def brisi_znak(niz, i):
    '''zbriše znak na i-tem mestu v nizu in ga shrani v zacasni pomnilnik'''

    if i >= len(niz):
        return niz

    global zacasni_pomnilnik
    zacasni_pomnilnik = niz[i]
    return niz[:i] + niz[i+1:]


def vrini_izbrisano(niz, i):
    '''na i-to mesto v nizu vrine znake iz začasnega pomnilnika'''

    if i > len(niz):
        return niz
    elif i == len(niz):
        return niz + zacasni_pomnilnik
    else:
        return niz[:i] + zacasni_pomnilnik + niz[i:]


def vrini_presledek(niz, i):
    '''na i-to mesto v nizu vrine presledek'''

    if i > len(niz):
        return niz
    elif i == len(niz):
        return niz + ' '
    else:
        return niz[:i] + ' ' + niz[i:]

################################################################################

def pregledna_stevila(stevilo):
    '''število naredi bolj pregledno, tako da na vsake tri mesta vrine presledek'''

    n = len(stevilo)
    pregledno_stevilo = stevilo[::-1]

    i = 3
    st_presledkov = 0
    while i < n:
        pregledno_stevilo = vrini_presledek(pregledno_stevilo, i+st_presledkov)
        i += 3
        st_presledkov += 1
    return pregledno_stevilo[::-1]


# še boljša možna rešitev:
def pregledna_stevila_1(stevilo):
    '''število naredi bolj pregledno, tako da na vsake tri mesta vrine presledek'''

    i = 3
    while i < len(stevilo):
        stevilo = vrini_presledek(stevilo, -i)
        i += 4
    return stevilo

1998.1.3

1. podnaloga

Podjetja vsako leto zaslužijo nekaj denarja. Ob koncu leta, ko je obračun, morajo prikazati dobiček. Zaradi hecnih zakonov se jim ne splača prikazati dobička, ki je večji kot 1000 cekinov. Naše podjetje ”Hlevi softwearskih ljubiteljev“ (hsl) si vsako leto izplača največji dobiček, ki ne presega 1000 cekinov, preostanek denarja pa prenese v naslednje leto.

Naloga

Preuredi vrstice funkcije knjigovodstvo(letni_dobicki), ki prebere, koliko denarja je zaslužilo podjetje, vrne pa dobiček ob koncu leta in koliko denarja se je preneslo v naslednje leto. Pri naslednjem letu seveda upošteva tudi denar, ki se je prenesel iz prejšnjega leta.

else:
dobicek_prenos.append((dobicek,prenos))
def knjigovodstvo(letni_dobicki):
if prenos > 1000:
dobicek_prenos = []
return dobicek_prenos
prenos += dobicek
prenos = 0
prenos -= dobicek
dobicek = prenos
dobicek = 1000
for dobicek in letni_dobicki:

Vhodni podatki

Seznam letnih dobičkov.

Izhodni podatki

Seznam parov (dobiček, prenos).

Primer

Vhod

[300,800,1200,1500,400,100,50,500,1500]

Izhod

[(300,0),(800,0),(1000,200),(1000,700),(1000,100),(200,0),(50,0),(500,0),
(1000,500)]

Uradna rešitev

def knjigovodstvo(letni_dobicki):
    '''Prejme seznam letnih dobičkov in vrne seznam parov (dobiček, prenos).'''

    prenos = 0
    dobicek_prenos = []
    for dobicek in letni_dobicki:
        prenos += dobicek
        if prenos > 1000:
            dobicek = 1000
        else:
            dobicek = prenos
        prenos -= dobicek
        dobicek_prenos.append((dobicek,prenos))
    return dobicek_prenos

1998.2.1

1. podnaloga

Podane so celoštevilske koordinate $n$ točk, ki ležijo v ravnini. Vsak par teh točk določa pravokotnik, ki ima s koordinatnima osema vzporedne stranice in ena točka leži v njegovem spodnjem levem oglišču, druga pa v zgornjem desnem oglišču.

Naloga

Preuredi vrstice funkcije kvadrati(sez_X, sez_Y), ki vrne število takih pravokotnikov, ki so kvadrati. Šteje tudi izrojene kvadrate, pri katerih spodnje levo in zgornje desno oglišče sovpadata.

koordinata_X2 = sez_X[j]
st_kvadratov += 1
koordinata_X1 = sez_X[i]
n = len(sez_X)
return st_kvadratov
koordinata_Y1 = sez_Y[i]
st_kvadratov = 0
if abs(koordinata_X1 - koordinata_X2) == abs(koordinata_Y1 - koordinata_Y2):
for i in range(n):
def kvadrati(sez_X, sez_Y):
koordinata_Y2 = sez_Y[j]
for j in range(i + 1, n):

Vhodni podatki

Seznama X in Y koordinat danih točk. Predpostavimo, da sta enako dolga, torej da sta za vse točke določeni obe koordinati. Število na i-tem mestu v seznamu X predstavlja x koordinato i-te točke, število na i-tem mestu v seznamu Y pa y koordinato i-te točke.

Območje, na katerem ležijo točke v ravnini, je znotraj kvadrata: $-1000 <= x,y <= 1000$

Izhodni podatki

Število kvadratov.

Primer

Vhod

>>> kvadrati([1,2,3,5],[0,2,3,4])

Izhod

2

Uradna rešitev

# Taki dve točki torej prepoznamo po
# tem, da imata obe enako razliko med x- in y-koordinato.

def kvadrati(sez_X, sez_Y):
    '''Glede na točke vrne število kvadratov.'''

    n = len(sez_X)
    st_kvadratov = 0
    for i in range(n):
        koordinata_X1 = sez_X[i]
        koordinata_Y1 = sez_Y[i]
        for j in range(i + 1, n):
            koordinata_X2 = sez_X[j]
            koordinata_Y2 = sez_Y[j]
            if abs(koordinata_X1 - koordinata_X2) == abs(koordinata_Y1 - koordinata_Y2):
                st_kvadratov += 1
    return st_kvadratov


# še ena možna rešitev:
def kvadrati_1(sez_X, sez_Y):
    '''Prejme podatke o točkah v koordinatnem sistemu in vrne število kvadratov.'''

    a = [0 for k in range(-2000,2001)]

    st_kvadratov = 0    # število najdenih kvadratov
    for j in range(len(sezX)):
        i = sez_X[j] - sez_Y[j]
        st_kvadratov += a[i]
        a[i] += 1
    return st_kvadratov# Naj bosta (x, y) in (x0, y0) dve točki, ki ležita v spodnjem levem in zgornjem
# desnem oglišču nekega kvadrata s stranico a. Potem mora veljati x0 = x+a in
# y0 = y+a, torej x0−y0 = (x+a)−(y+a) = x−y. Taki dve točki torej prepoznamo po
# tem, da imata obe enako razliko med x- in y-koordinato; z drugimi besedami,
# če bi skozi vsako točko poslali premico, ki oklepa z absciso kot 45 stopinj,
# bi bila to obakrat ena in ista premica.
#
# Zato lahko ravnamo takole: pripravimo si tabelo a[−2000..2000], katere
# elementi bodo cela števila; na začetku postavimo vse elemente na nič.
# Z elementom a[i] bomo šteli, koliko točk leži na premici x−y = i.
# Imejmo še nek števec, ki pove, koliko kvadratov smo že našli (recimo mu S).
# Potem za vsako točko (x, y) izračunamo x − y in vemo, da smo doslej odkrili
# a[x − y] točk z enako razliko med koordinatama in da naša nova točka tvori po
# en kvadrat z vsako od njih.
#
# Torej povečajmo S za a[x − y], nato pa povečajmo a[x − y] za 1, da v mislih
# dodamo pravkar prebrano točko med tiste s takšno razliko koordinat.

def kvadrati(X, Y):
    '''Prejme podatke o točkah v koordinatnem sistemu in vrne število kvadratov.'''

    a = [0 for k in range(-2000,2001)]

    s = 0    # število najdenih kvadratov
    for j in range(len(X)):
        i = X[j] - Y[j]
        s += a[i]
        a[i] += 1
    return s